package com.example.system.class22;

import java.util.HashMap;
import java.util.Map;

/**
 * @Date 2022/8/23
 * @Author Jonathan
 * @Description 统计每一种面额的张数
 */
public class Code04_CoinsWaySameValueSamePaper {
    public static void main(String[] args) {
        int[] arr = new int[]{1, 1, 1, 1, 2, 2, 2};
        System.out.printf("方法有:%d种\n", ways(arr, 4));
    }


    public static int ways(int[] arr, int aim) {
        //  边界校验
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        final Info info = getInfo(arr);
        return process(info.coins, info.count, 0, aim);
    }


    public static int process(int[] coins, int[] count, int index, int rest) {
        if (index == coins.length) {
            return rest == 0 ? 1 : 0;
        }

        int ans = 0;
        // 不超过张数且不超过rest的钱数
        for (int zhang = 0; coins[index] * zhang <= rest && zhang <= count[index]; zhang++) {
            ans += process(coins, count, index + 1, rest - coins[index] * zhang);
        }
        return ans;
    }


    /**
     * 统计每一种面额的张数
     */
    public static Info getInfo(int[] arr) {
        Map<Integer, Integer> coinsCountMap = new HashMap<>();
        for (int coin : arr) {
            if (coinsCountMap.containsKey(coin)) {
                coinsCountMap.put(coin, coinsCountMap.get(coin) + 1);

            } else {
                coinsCountMap.put(coin, 1);
            }
        }
        int size = coinsCountMap.keySet().size();
        int[] coins = new int[size];
        int[] count = new int[size];
        int index = 0;
        for (Integer coin : coinsCountMap.keySet()) {
            coins[index] = coin;
            count[index] = coinsCountMap.get(coin);
            index++;
        }
        return new Info(coins, count);

    }


    public static class Info {
        private int[] coins;
        private int[] count;

        public Info(int[] coins, int[] count) {
            this.coins = coins;
            this.count = count;
        }
    }


}
